package com.mlick.a.leetcode;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 2589. 完成所有任务的最少时间
 *你有一台电脑，它可以 同时 运行无数个任务。给你一个二维整数数组 tasks ，其中 tasks[i] = [starti, endi, durationi] 表示第 i 个任务需要在 闭区间 时间段 [starti, endi] 内运行 durationi 个整数时间点（但不需要连续）。
 *
 * 当电脑需要运行任务时，你可以打开电脑，如果空闲时，你可以将电脑关闭。
 *
 * 请你返回完成所有任务的情况下，电脑最少需要运行多少秒。
 *
 * 示例 1：
 *
 * 输入：tasks = [[2,3,1],[4,5,1],[1,5,2]]
 * 输出：2
 * 解释：
 * - 第一个任务在闭区间 [2, 2] 运行。
 * - 第二个任务在闭区间 [5, 5] 运行。
 * - 第三个任务在闭区间 [2, 2] 和 [5, 5] 运行。
 * 电脑总共运行 2 个整数时间点。
 * 示例 2：
 *
 * 输入：tasks = [[1,3,2],[2,5,3],[5,6,2]]
 * 输出：4
 * 解释：
 * - 第一个任务在闭区间 [2, 3] 运行
 * - 第二个任务在闭区间 [2, 3] 和 [5, 5] 运行。
 * - 第三个任务在闭区间 [5, 6] 运行。
 * 电脑总共运行 4 个整数时间点。
 *  
 *
 * 提示：
 *
 * 1 <= tasks.length <= 2000
 * tasks[i].length == 3
 * 1 <= starti, endi <= 2000
 * 1 <= durationi <= endi - starti + 1
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/minimum-time-to-complete-all-tasks
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class A2589 {


    /**
     * 暴力 + 贪心
     * 1.右端排序
     * 2.从左到右检查是否有被占用
     * 3.再从右到耗时，增加
     */
    public class Solution {
        public int findMinimumTime(int[][] tasks) {
            Arrays.sort(tasks, (o1,o2) -> o1[1] - o2[1]);

            //记录某个时间段是否已经执行
            boolean[] run = new boolean[tasks[tasks.length-1][1] + 1];

            int min = 0;
            for (int[] task : tasks) {
                int s = task[0], e = task[1], d = task[2];

                for (int i = s; i <= e; i++) {
                    if (run[i]){
                        d--;
                    }
                }

                for (int i = d; d > 0; i--) {
                    if (!run[i]){
                        d--;
                        run[i] = true;
                        min ++;
                    }
                }

            }
            return min;
        }
    }

    public static void main(String[] args) {
        int[][] tasks = {{1,3,2},{2,5,3},{5,6,2}};
        Arrays.sort(tasks, (o1, o2) -> o1[1] - o2[1]);
        System.out.println(Arrays.deepToString(tasks));
    }
}
